package atop;

import leetcode.ListNode;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/15 21:19
 * @描述 判断相遇后派一个小鬼跟fast指针相同的位置，返回它就可以了
 */
public class 寻找链表环入口 {
    public ListNode detectCycle(ListNode head) {
        boolean isloop=false;
        ListNode fast=new ListNode(0);//头指针
        ListNode slow=fast;
        fast.next=head;
        if(fast.next==null||fast.next.next==null)
            return null;
        while (fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
            {
                isloop=true;
                break;
            }
        }
        if(!isloop)//如果没有环返回
            return null;


        ListNode team=new ListNode(-1);//新建一个Node遍历到二者相遇返回这个即可 头指针 下一个才是head
        team.next=head;
        while (team!=fast) {//slow 和fast 分别从起点和当前点出发
            team=team.next;
            fast=fast.next;
        }
        return team;
    }
}
